package algos_dasgupta;

public class EditDistance {

	public int findEditDistance(String s, String d)
	{
		int[][] m = new int[s.length()][d.length()];
		
		for(int i = 0; i < s.length(); i++) {
			m[i][0] = i;
		}
		for(int j = 0; j < d.length(); j++) {
			m[0][j] = j;
		}
		
		for(int i = 1; i < s.length(); i++) {
			for(int j = 1; j < d.length(); j++) {
				m[i][j] = min( 1 + m[i-1][j], 1 + m[i][j-1] , diff(s, i, d,j) + m[i-1][j-1] ); 
			}
		}
		
		return m[s.length()-1][d.length() -1];
	}
	
	private int diff(String s, int i, String d, int j) {
		if(s.charAt(i) == d.charAt(j))
			return 0;
		return 1;
	}

	public int min(int a, int b, int c)
	{
		if(a < b && a < c)
			return a;
		if(b < a && b < c)
			return b;
		return c;
	}
	public static void main(String[] args) {
		EditDistance ed = new EditDistance();
		System.out.println(ed.findEditDistance("thou shalt not", "you should not"));
		

	}

}
